package com.str.graphs;

import com.str.queue.ArrayQueue;
import com.str.queue.Queue;

public class Traversal {
  private static void preVisit(Graph g, int v) {
    System.out.println("PreVisit vertex " + v);
  }

  private static void postVisit(Graph g, int v) {
    System.out.println("PostVisit vertex " + v);
  }

  public static void dfs(Graph g) {
    boolean[] visited = new boolean[g.n()];
    for (int v=0; v < g.n(); v++)
      visited[v] = false;
    for (int v=0; v < g.n(); v++)
      if (!visited[v])
        dfs(g, v, visited);        
  }	

  private static void dfs(Graph g, int v, boolean[] visited) { // Depth first search
    preVisit(g, v);           // Take appropriate action
    visited[v] = true;
    for (int w = g.first(v); w < g.n(); w = g.next(v, w))
      if (!visited[w])
        dfs(g, w, visited);
    postVisit(g, v);          // Take appropriate action
  }
  
  public static void bfs(Graph g) {
    boolean[] visited = new boolean[g.n()];
    Queue queue = new ArrayQueue();   
    for (int v=0; v < g.n(); v++)
      visited[v] = false;
    for (int v=0; v < g.n(); v++)
      if (!visited[v])
        bfs(g, v, visited, queue);
  }	
  
  private static void bfs(Graph g, int start, boolean[] visited, Queue queue) { // Depth first search
    queue.enqueue(new Integer(start));           // Initialize Q
    visited[start] = true;
    while (!queue.isEmpty()) {    // Process all vertices on Q
      Integer i = (Integer) (queue.dequeue());
      int v = i.intValue();
      preVisit(g, v);           // Take appropriate action
      for (int w = g.first(v); w < g.n(); w = g.next(v, w))
        if (!visited[w]) {
	      visited[w] = true;
	      queue.enqueue(new Integer(w));
        }
      postVisit(g, v);          // Take appropriate action
    }
  }
}
